import java.util.*;

public class LeetCode51 {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        int[] nums = new int[n];
        Arrays.fill(nums,-1);
        Set<Integer> p = new HashSet<>();
        Set<Integer> p1 = new HashSet<>();
        Set<Integer> p2 = new HashSet<>();
        backtrack(res,n,0,nums,p,p1,p2);
        return res;
    }

    private void backtrack(List<List<String>> res, int n, int row, int[] nums, Set<Integer> p, Set<Integer> p1, Set<Integer> p2) {
        if(row == n) {
            List<String> a = makeans(nums,n);
            res.add(a);
        }else {
            for (int i = 0; i < n; i++) {
                if(p.contains(i)) {
                    continue;
                }
                int d1 = row - i;
                if(p1.contains(d1)) {
                    continue;
                }
                int d2 = row + i;
                if(p2.contains(d2)) {
                    continue;
                }
                nums[row] = i;
                p.add(i);
                p1.add(d1);
                p2.add(d2);
                backtrack(res,n,row + 1,nums,p,p1,p2);
                nums[row] = -1;
                p.remove(i);
                p1.remove(d1);
                p2.remove(d2);
            }
        }
    }

    private List<String> makeans(int[] nums, int n) {
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] chars = new char[n];
            Arrays.fill(chars,'.');
            chars[nums[i]] = 'Q';
            ans.add(new String(chars));
        }
        return ans;
    }
}
